package madixin.t104;

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    /**
     * 递归算法
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * 非递归算法,广度优先遍历，BFS
     */
    public int maxDepthNoRecursion(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int maxDepth = 1;
        Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
        stack.add(new Pair<>(root, 1));
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> cur = stack.poll();
            TreeNode curNode = cur.getKey();
            int curDepth = cur.getValue();
            maxDepth = Math.max(maxDepth, curDepth);

            if (curNode.left != null) {
                stack.add(new Pair<>(curNode.left, curDepth + 1));
            }

            if (curNode.right != null) {
                stack.add(new Pair<>(curNode.right, curDepth + 1));
            }
        }
        return maxDepth;
    }
}